<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>算法设计与分析实验2 | hatena</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="*实验项目* 分治法的应用 *指导老师*     *实验目的* 学习分治法的思想和应用     一、实验内容1.某石油公司有n口油井，为方便输送石油，计划修建输油管道。根据设计要求，水平方向有一条主管道，每口油井修一条垂直方向的支线管道通向主管道。请设计一种算法确定主管道的位置，使得所有油井到主管道之间的支线管道长度的总和最小 2.Karatsuba乘法用于实现两个大整数相乘。所谓大整数相乘">
<meta property="og:type" content="article">
<meta property="og:title" content="算法设计与分析实验2">
<meta property="og:url" content="https://gitee.com/lanceluot/blog.git/2024/04/14/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C2/index.html">
<meta property="og:site_name" content="hatena">
<meta property="og:description" content="*实验项目* 分治法的应用 *指导老师*     *实验目的* 学习分治法的思想和应用     一、实验内容1.某石油公司有n口油井，为方便输送石油，计划修建输油管道。根据设计要求，水平方向有一条主管道，每口油井修一条垂直方向的支线管道通向主管道。请设计一种算法确定主管道的位置，使得所有油井到主管道之间的支线管道长度的总和最小 2.Karatsuba乘法用于实现两个大整数相乘。所谓大整数相乘">
<meta property="og:locale" content="zn_CN">
<meta property="article:published_time" content="2024-04-14T11:48:53.000Z">
<meta property="article:modified_time" content="2024-04-15T12:49:37.538Z">
<meta property="article:author" content="myself">
<meta property="article:tag" content="实验">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/blog/atom.xml" title="hatena" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/blog/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/blog/css/style.css">

  
    
<link rel="stylesheet" href="/blog/fancybox/jquery.fancybox.min.css">

  
  
<meta name="generator" content="Hexo 6.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/blog/" id="logo">hatena</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"><span class="fa fa-bars"></span></a>
        
          <a class="main-nav-link" href="/blog/">Home</a>
        
          <a class="main-nav-link" href="/blog/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
        
          <a class="nav-icon" href="/blog/atom.xml" title="RSS Feed"><span class="fa fa-rss"></span></a>
        
        <a class="nav-icon nav-search-btn" title="Suche"><span class="fa fa-search"></span></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Suche"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="https://gitee.com/lanceluot/blog.git"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-算法设计与分析实验2" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/blog/2024/04/14/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C2/" class="article-date">
  <time class="dt-published" datetime="2024-04-14T11:48:53.000Z" itemprop="datePublished">2024-04-14</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      算法设计与分析实验2
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <table>
<thead>
<tr>
<th><em><strong>*实验项目*</strong></em></th>
<th>分治法的应用</th>
<th><em><strong>*指导老师*</strong></em></th>
<th></th>
</tr>
</thead>
<tbody><tr>
<td><em><strong>*实验目的*</strong></em></td>
<td>学习分治法的思想和应用</td>
<td></td>
<td></td>
</tr>
</tbody></table>
<h2 id="一、实验内容"><a href="#一、实验内容" class="headerlink" title="一、实验内容"></a>一、实验内容</h2><p>1.某石油公司有n口油井，为方便输送石油，计划修建输油管道。根据设计要求，水平方向有一条主管道，每口油井修一条垂直方向的支线管道通向主管道。请设计一种算法确定主管道的位置，使得所有油井到主管道之间的支线管道长度的总和最小</p>
<p>2.Karatsuba乘法用于实现两个大整数相乘。所谓大整数相乘是指整数比较大，相乘的结果超出了基本数据类型的表示范围，所以不能直接做乘法运算。算法的基本原理是将大整数拆分成两段后变成较小的整数，请设计分治算法说明Karatsuba乘法的原理，并实现该算法。</p>
<h2 id="二、问题分析"><a href="#二、问题分析" class="headerlink" title="二、问题分析"></a>二、问题分析</h2><h3 id="1-铺设油井管道"><a href="#1-铺设油井管道" class="headerlink" title="1.铺设油井管道"></a>1.铺设油井管道</h3><p>这个显然是将管道铺在中间最合适，因为极端情况管道在最上方和最下方都会使得距离很大，那么管道的位置也显然之能是所有油井的中间位置，那么问题就转换为求所有的油井的中位数了，我们可以先进行排序然后在取中间值，但是由于排序算法的时间复杂度最快也是O(ologn)，这不满足题目要求，要使用O(n)的算法，我们可以使用分治策略求解，具体就是快速选择算法，它可以让我们在O(n）的时间内选出第k大的数。</p>
<h3 id="2-Karatsuba乘法"><a href="#2-Karatsuba乘法" class="headerlink" title="2.Karatsuba乘法"></a>2.Karatsuba乘法</h3><p>由karartsuba算法的原理我们知道，对于竖式乘法，如果把数分成两部分分别相乘，那么会进行4次乘法，三次加法，而使用Karatsuba算法,可以减少一次乘法，7次加法，这使得大数乘法的时间可以得到优化，我们可以使用分治法来实现这个算法，即进行两个大数的乘法，可以转换为三次小的乘法和一些加法来完成，然后递归进行即可</p>
<span id="more"></span>

<h2 id="三、数据结构定义"><a href="#三、数据结构定义" class="headerlink" title="三、数据结构定义"></a>三、数据结构定义</h2><h3 id="1-铺设油井管道-1"><a href="#1-铺设油井管道-1" class="headerlink" title="1.铺设油井管道"></a>1.铺设油井管道</h3><p>Int arr[n];&#x2F;&#x2F;所有油井的距离<br>Int median;&#x2F;&#x2F;油井距离的中位数<br>Int minx;&#x2F;&#x2F;距离总和最小值<br>int quickSelect（int a[],int left,int right)&#x2F;&#x2F;寻找数组 arr 中第 k 小的元素</p>
<h3 id="3-karatsuba算法"><a href="#3-karatsuba算法" class="headerlink" title="3.karatsuba算法"></a>3.karatsuba算法</h3><p>string  karatsuba(string a,string b)&#x2F;&#x2F;karatsuba算法，计算两个大数的乘积以字符串保存结果<br>string operator+(const string&amp; num1, const string&amp; num2)；&#x2F;&#x2F;重载运算符进行大数加法<br>string operator-(const string&amp; num1, const string&amp; num2)；&#x2F;&#x2F;重载运算符进行两个大数的减法</p>
<h2 id="四、算法伪代码描述"><a href="#四、算法伪代码描述" class="headerlink" title="四、算法伪代码描述"></a>四、算法伪代码描述</h2><h3 id="1-铺设油井管道-2"><a href="#1-铺设油井管道-2" class="headerlink" title="1.铺设油井管道"></a>1.铺设油井管道</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">函数 quickSelect(arr, left, right, k):</span><br><span class="line">    如果 left 等于 right，则返回 arr[left]</span><br><span class="line">// 分治法的思想：将数组分成两部分，对其中一部分进行处理</span><br><span class="line">// 选取中枢元素</span><br><span class="line">pivotIndex = left + (right - left) / <span class="number">2</span></span><br><span class="line">pivot = arr[pivotIndex]</span><br><span class="line"></span><br><span class="line">// 将中枢元素移动到数组末尾</span><br><span class="line">交换 arr[pivotIndex] 和 arr[right]</span><br><span class="line"></span><br><span class="line">// 分区过程</span><br><span class="line">i = left</span><br><span class="line">对于 j 从 left 到 right - <span class="number">1</span>：</span><br><span class="line">    如果 arr[j] &lt; pivot：</span><br><span class="line">        交换 arr[i] 和 arr[j]</span><br><span class="line">        i++</span><br><span class="line"></span><br><span class="line">交换 arr[i] 和 arr[right]</span><br><span class="line"></span><br><span class="line">// 判断中枢元素的位置与 k 的大小关系</span><br><span class="line">如果 i 等于 k，则返回 arr[i]</span><br><span class="line">否则如果 i 小于 k，则递归调用 quickSelect(arr, i + <span class="number">1</span>, right, k)</span><br><span class="line">否则递归调用 quickSelect(arr, left, i - <span class="number">1</span>, k)</span><br><span class="line">函数 findMedian(arr, n):</span><br><span class="line">    返回 quickSelect(arr, <span class="number">0</span>, n - <span class="number">1</span>, n / <span class="number">2</span>)</span><br><span class="line"></span><br><span class="line">主函数：</span><br><span class="line">    输入 n</span><br><span class="line">    分配数组 arr 大小为 n</span><br><span class="line">    对于 i 从 <span class="number">0</span> 到 n - <span class="number">1</span>：</span><br><span class="line">        输入 a 和 b</span><br><span class="line">        将 b 放入 arr[i]</span><br><span class="line">        median = findMedian(arr, n)</span><br><span class="line">	minx = <span class="number">0</span></span><br><span class="line">	对于 i 从 <span class="number">0</span> 到 n - <span class="number">1</span>：</span><br><span class="line">    minx += <span class="built_in">abs</span>(median - arr[i])</span><br><span class="line"></span><br><span class="line">    输出 minx</span><br><span class="line">    释放数组 arr</span><br></pre></td></tr></table></figure>


<p>​    </p>
<h3 id="2-karatsuba算法"><a href="#2-karatsuba算法" class="headerlink" title="2.karatsuba算法"></a>2.karatsuba算法</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br></pre></td><td class="code"><pre><span class="line">// 定义大数加法</span><br><span class="line">string operator+(const string&amp; num1, const string&amp; num2) &#123;</span><br><span class="line">    string result; // 存储结果</span><br><span class="line">    <span class="built_in">int</span> carry = <span class="number">0</span>; // 进位</span><br><span class="line"></span><br><span class="line">    // 从低位到高位逐位相加</span><br><span class="line">    <span class="built_in">int</span> i = num1.size() - <span class="number">1</span>;</span><br><span class="line">    <span class="built_in">int</span> j = num2.size() - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (i &gt;= <span class="number">0</span> || j &gt;= <span class="number">0</span> || carry &gt; <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="built_in">int</span> <span class="built_in">sum</span> = carry; // 当前位的和等于进位</span><br><span class="line">        <span class="keyword">if</span> (i &gt;= <span class="number">0</span>) &#123;</span><br><span class="line"></span><br><span class="line">// 将字符转换为数字并加到当前位的和中</span><br><span class="line">            <span class="built_in">sum</span> += num1[i] - <span class="string">&#x27;0&#x27;</span>;i--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (j &gt;= <span class="number">0</span>) &#123;</span><br><span class="line">// 将字符转换为数字并加到当前位的和中</span><br><span class="line">            <span class="built_in">sum</span> += num2[j] - <span class="string">&#x27;0&#x27;</span>;j--;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line"></span><br><span class="line">        // 更新进位和当前位的值</span><br><span class="line">        carry = <span class="built_in">sum</span> / <span class="number">10</span>; // 计算进位</span><br><span class="line">        <span class="built_in">sum</span> %= <span class="number">10</span>; // 更新当前位的值</span><br><span class="line"></span><br><span class="line">// 将当前位的值转换为字符并添加到结果中</span><br><span class="line">        result += to_string(<span class="built_in">sum</span>);     &#125;</span><br><span class="line"></span><br><span class="line">    // 反转结果字符串，得到正确的加法结果</span><br><span class="line">    reverse(result.begin(), result.end());</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">// 定义大数减法</span><br><span class="line">string operator-(const string&amp; num1, const string&amp; num2) &#123;</span><br><span class="line">    // 实现减法逻辑</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">// 定义 Karatsuba 算法</span><br><span class="line">string karatsuba(string a, string b) &#123;</span><br><span class="line">    // 获取输入字符串的长度</span><br><span class="line">    <span class="built_in">int</span> n = a.size();</span><br><span class="line">    <span class="built_in">int</span> m = b.size();</span><br><span class="line">    string ans = <span class="string">&quot;0&quot;</span>;</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line">    // 如果输入的字符串长度为 <span class="number">1</span>，则直接相乘</span><br><span class="line">    <span class="keyword">if</span> (n == <span class="number">1</span>) &#123;</span><br><span class="line">        // 实现直接相乘逻辑</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (m == <span class="number">1</span>) &#123;</span><br><span class="line">        // 实现直接相乘逻辑</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    // 对输入字符串进行补零，使得两个字符串长度相等</span><br><span class="line">    <span class="keyword">if</span> (n &gt; m) &#123;</span><br><span class="line">        // 实现补零逻辑</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (n &lt; m) &#123;</span><br><span class="line">        // 实现补零逻辑</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    // 分割输入字符串为两部分</span><br><span class="line">    string a1 = a.substr(<span class="number">0</span>, n / <span class="number">2</span>);</span><br><span class="line">    string a2 = a.substr(n / <span class="number">2</span>, n - n / <span class="number">2</span>);</span><br><span class="line">    string b1 = b.substr(<span class="number">0</span>, m / <span class="number">2</span>);</span><br><span class="line">    string b2 = b.substr(m / <span class="number">2</span>, m - m / <span class="number">2</span>);</span><br><span class="line">    </span><br><span class="line">    // 递归调用 Karatsuba 算法</span><br><span class="line">    string a1b1 = karatsuba(a1, b1);</span><br><span class="line">    string a2b2 = karatsuba(a2, b2);</span><br><span class="line">    string a1a2 = a1 + a2;</span><br><span class="line">    string b1b2 = b1 + b2;</span><br><span class="line">    string a1a2b1b2 = karatsuba(a1a2, b1b2);</span><br><span class="line">    </span><br><span class="line">    // 使用分治法思想计算乘积</span><br><span class="line">    a1a2b1b2 = a1a2b1b2 - a1b1 - a2b2;</span><br><span class="line">    <span class="keyword">for</span> (<span class="built_in">int</span> i = <span class="number">0</span>; i &lt; <span class="number">2</span> * (n - n / <span class="number">2</span>); i++) &#123;</span><br><span class="line">        a1b1 += <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="built_in">int</span> i = <span class="number">0</span>; i &lt; (n - n / <span class="number">2</span>); i++) &#123;</span><br><span class="line">        a1a2b1b2 += <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    ans = a1b1 + a1a2b1b2;</span><br><span class="line">    ans = ans + a2b2;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">// 主函数</span><br><span class="line"><span class="built_in">int</span> main() &#123;</span><br><span class="line">    // 输入两个大数</span><br><span class="line">    string a, b;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    cin &gt;&gt; b;</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line">    // 调用 Karatsuba 算法计算乘积</span><br><span class="line">    string ans = karatsuba(a, b);</span><br><span class="line">    </span><br><span class="line">    // 去除结果前面的多余零，并输出结果</span><br><span class="line">    <span class="keyword">while</span> (ans[<span class="number">0</span>] == <span class="string">&#x27;0&#x27;</span>) ans.erase(<span class="number">0</span>, <span class="number">1</span>);</span><br><span class="line">    cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="五、算法时间和空间复杂度分析（要求写出详细过程）"><a href="#五、算法时间和空间复杂度分析（要求写出详细过程）" class="headerlink" title="五、算法时间和空间复杂度分析（要求写出详细过程）"></a>五、算法时间和空间复杂度分析（要求写出详细过程）</h2><h3 id="1-铺设油井管道-3"><a href="#1-铺设油井管道-3" class="headerlink" title="1.铺设油井管道"></a>1.铺设油井管道</h3><p>由于我们采用的快速选择算法来进行分治处理，时间复杂度也就是快速选择算法的时间复杂度，快速选择算法，每次选择一个基元遍历整个数组分区后就可以判断，如果结果不是基元则递归判断比基元小的数据部分或则比基元数据大的部分，则可以得到递推式T(n)&#x3D;T(n&#x2F;2)+n，递推下去则得到<br>T(n)&#x3D;T(n&#x2F;2)+n&#x3D;T(n&#x2F;4)+n&#x2F;2+n&#x3D;T(1)+….+n&#x2F;2+n&#x3D;1+2+…n&#x2F;2+n&#x3D;1(1-2^t)&#x2F;(1-2),其中t&#x3D;log2n(2为底),最后得到T(n)&#x3D;2n-1,即时间复杂度为O(n)&#x3D;n;</p>
<h3 id="2-karatsuba算法-1"><a href="#2-karatsuba算法-1" class="headerlink" title="2.karatsuba算法"></a>2.karatsuba算法</h3><p>karatsuba算法将两个数的乘法变成3个数的乘法和7次加法，显然递推式为T(n)&#x3D;3T(n&#x2F;2)+7&#x3D;3^t+7t其中t&#x3D;log2n(2为底),则T(n)&#x3D;n^log23+7log23,即时间复杂度为O(n^log23)。</p>
<h2 id="六、错误记录和解决"><a href="#六、错误记录和解决" class="headerlink" title="六、错误记录和解决"></a>六、错误记录和解决</h2><p>1.对于油井管道铺设问题，一开始使用c++的cin处理输入，但是总是超时，后来改成c语言时间就变短了<br>2.karatsuba算法，一开始想的是直接按照整数乘法使用数据范围更大的long long来模拟karatsuba算法，对于不是特别大的数字还能正确显示结果，后来我发现题目的输入数据远远超过long long的范围，并且这种做法不具有通用性，最后还是采用字符串保存结果</p>
<h2 id="七、心得体会"><a href="#七、心得体会" class="headerlink" title="七、心得体会"></a>七、心得体会</h2><p>分治算法是基础算法，它可以帮助我们有效分析问题，并分治处理，使得我们不用关心所有细节，这一点和递归很相似，尽管分治法很多时候都是用递归实现。</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://gitee.com/lanceluot/blog.git/2024/04/14/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C2/" data-id="cluzhunt50005ko5bg3165qcn" data-title="算法设计与分析实验2" class="article-share-link"><span class="fa fa-share">Teilen</span></a>
      
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/blog/tags/%E5%AE%9E%E9%AA%8C/" rel="tag">实验</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/blog/2024/04/14/leetcode530/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Neuer</strong>
      <div class="article-nav-title">
        
          leetcode530二叉搜索树的最小绝对值
        
      </div>
    </a>
  
  
    <a href="/blog/2024/03/18/%E7%AB%9E%E8%B5%9B%E4%B9%8B%E5%8F%96%E6%95%B4%E5%87%BD%E6%95%B0/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Älter</strong>
      <div class="article-nav-title">竞赛之取整函数</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Kategorien</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/blog/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA/">计算机</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/BUG/" rel="tag">BUG</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/RPC/" rel="tag">RPC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/git/" rel="tag">git</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/java/" rel="tag">java</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/java%E5%90%8E%E7%AB%AF%E5%BC%80%E5%8F%91/" rel="tag">java后端开发</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/java%E6%BA%90%E7%A0%81/" rel="tag">java源码</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/jvm/" rel="tag">jvm</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/leetcode/" rel="tag">leetcode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/leetcode%E9%A2%98%E8%A7%A3/" rel="tag">leetcode题解</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/rabbitmq/" rel="tag">rabbitmq</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/redis/" rel="tag">redis</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/shell/" rel="tag">shell</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/spring/" rel="tag">spring</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/springboot/" rel="tag">springboot</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/test/" rel="tag">test</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E4%BD%9C%E4%B8%9A/" rel="tag">作业</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E5%AE%9E%E9%AA%8C/" rel="tag">实验</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E5%AE%9E%E9%AA%8C3/" rel="tag">实验3</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%84%9F%E6%83%B3/" rel="tag">感想</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" rel="tag">操作系统</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%B5%8B%E8%AF%95/" rel="tag">测试</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E7%96%91%E9%97%AE/" rel="tag">疑问</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E7%AC%94%E8%AE%B0/" rel="tag">笔记</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" rel="tag">设计模式</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E9%97%AE%E9%A2%98/" rel="tag">问题</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/blog/tags/BUG/" style="font-size: 10px;">BUG</a> <a href="/blog/tags/RPC/" style="font-size: 10px;">RPC</a> <a href="/blog/tags/git/" style="font-size: 10px;">git</a> <a href="/blog/tags/java/" style="font-size: 20px;">java</a> <a href="/blog/tags/java%E5%90%8E%E7%AB%AF%E5%BC%80%E5%8F%91/" style="font-size: 10px;">java后端开发</a> <a href="/blog/tags/java%E6%BA%90%E7%A0%81/" style="font-size: 10px;">java源码</a> <a href="/blog/tags/jvm/" style="font-size: 10px;">jvm</a> <a href="/blog/tags/leetcode/" style="font-size: 10px;">leetcode</a> <a href="/blog/tags/leetcode%E9%A2%98%E8%A7%A3/" style="font-size: 15px;">leetcode题解</a> <a href="/blog/tags/rabbitmq/" style="font-size: 10px;">rabbitmq</a> <a href="/blog/tags/redis/" style="font-size: 10px;">redis</a> <a href="/blog/tags/shell/" style="font-size: 10px;">shell</a> <a href="/blog/tags/spring/" style="font-size: 10px;">spring</a> <a href="/blog/tags/springboot/" style="font-size: 10px;">springboot</a> <a href="/blog/tags/test/" style="font-size: 10px;">test</a> <a href="/blog/tags/%E4%BD%9C%E4%B8%9A/" style="font-size: 10px;">作业</a> <a href="/blog/tags/%E5%AE%9E%E9%AA%8C/" style="font-size: 15px;">实验</a> <a href="/blog/tags/%E5%AE%9E%E9%AA%8C3/" style="font-size: 10px;">实验3</a> <a href="/blog/tags/%E6%84%9F%E6%83%B3/" style="font-size: 10px;">感想</a> <a href="/blog/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" style="font-size: 10px;">操作系统</a> <a href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" style="font-size: 10px;">数据结构与算法</a> <a href="/blog/tags/%E6%B5%8B%E8%AF%95/" style="font-size: 10px;">测试</a> <a href="/blog/tags/%E7%96%91%E9%97%AE/" style="font-size: 10px;">疑问</a> <a href="/blog/tags/%E7%AC%94%E8%AE%B0/" style="font-size: 10px;">笔记</a> <a href="/blog/tags/%E7%AE%97%E6%B3%95/" style="font-size: 10px;">算法</a> <a href="/blog/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" style="font-size: 15px;">设计模式</a> <a href="/blog/tags/%E9%97%AE%E9%A2%98/" style="font-size: 10px;">问题</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archiv</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/05/">May 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/04/">April 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/03/">March 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/02/">February 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/01/">January 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/10/">October 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/09/">September 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/08/">August 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/05/">May 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/04/">April 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2022/12/">December 2022</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">letzter Beitrag</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/blog/2024/05/01/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C%E4%B8%89-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">算法设计与分析实验三-动态规划</a>
          </li>
        
          <li>
            <a href="/blog/2024/05/01/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%AE%9E%E9%AA%8C3-%E6%96%87%E4%BB%B6io%E7%BC%96%E7%A8%8B/">嵌入式实验3-文件io编程</a>
          </li>
        
          <li>
            <a href="/blog/2024/04/30/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%AE%9E%E8%B7%B5-%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AAfat12%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/">操作系统实践-实现一个fat12文件系统</a>
          </li>
        
          <li>
            <a href="/blog/2024/04/25/LambdaQuery-%E5%92%8C-Query%E7%9A%84%E5%8C%BA%E5%88%AB/">LambdaQuery 和 Query的区别</a>
          </li>
        
          <li>
            <a href="/blog/2024/04/25/LambdaQuery%E5%92%8CQuery%E7%9A%84%E5%8C%BA%E5%88%AB/">LambdaQuery和Query的区别</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2024 myself<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/blog/" class="mobile-nav-link">Home</a>
  
    <a href="/blog/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/blog/js/jquery-3.6.4.min.js"></script>



  
<script src="/blog/fancybox/jquery.fancybox.min.js"></script>




<script src="/blog/js/script.js"></script>





  </div>
</body>
</html>